package com.mlh.dp.old;

/*
题目：给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

举例：输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13

*/

public class MinimumSumofDescentPath {

    public static int method1(int[][] matrix,int row,int col){
        int min=Integer.MAX_VALUE;
        int size=matrix.length-1;
        if(row==size){
            return matrix[row][col];
        }
        if(col==0){
            return Math.min(method1(matrix,row+1,col), method1(matrix,row+1,col+1))+matrix[row][col];
        }
        if(col==size){
            return Math.min(method1(matrix,row+1,col), method1(matrix,row+1,col-1))+matrix[row][col];
        }
        return Math.min(method1(matrix,row+1,col),Math.min(method1(matrix,row+1,col-1)
                ,method1(matrix,row+1,col+1)))+matrix[row][col];
    }

    public static int method2(int[][]matrix){
        int size=matrix.length-1;
        int[][] res=new int[size+1][size+1];
        int min=Integer.MAX_VALUE;
        for(int i=size;i>=0;--i){
            for(int j=size;j>=0;--j){
                if(i==size){
                    res[i][j]=matrix[i][j];
                } else if(j==size){
                    res[i][j]=Math.min(res[i+1][j],res[i+1][j-1])+matrix[i][j];
                }else if(j==0){
                    res[i][j]=Math.min(res[i+1][j],res[i+1][j+1])+matrix[i][j];
                }else{
                    res[i][j]=Math.min(res[i+1][j],Math.min(res[i+1][j-1],res[i+1][j+1]))+matrix[i][j];
                }
                if(i==0){
                    min=res[i][j]<min?res[i][j]:min;
                }
            }
        }
        return min;
    }




}
